|
Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence. == Basic properties == Given integers ''P'' and ''Q'', where ''P'' > 0 and , let ''U''''k''(''P'', ''Q'') and ''V''''k''(''P'', ''Q'') be the corresponding Lucas sequences. Let ''n'' be a positive integer and let be the Jacobi symbol. We define : If ''n'' is a prime such that the greatest common divisor of ''n'' and ''Q'' (that is, GCD(''n, Q'')) is 1, then the following congruence condition holds (see page 1391 of ): : If this equation does ''not'' hold, then ''n'' is ''not'' prime. If ''n'' is ''composite'', then this equation usually does ''not'' hold (see,〔 page 1392). These are the key facts that make Lucas sequences useful in primality testing. Some good references are chapter 8 of the book by Bressoud and Wagon (with Mathematica code),〔 〕 pages 142-152 of the book by Crandall and Pomerance,〔 〕 and pages 53–74 of the book by Ribenboim .〔 〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lucas pseudoprime」の詳細全文を読む スポンサード リンク
|